//
// Description: 5775. 准时抵达会议现场的最小跳过休息次数
// Created by Loading on 2021/5/30.
//

#include <bits/stdc++.h>

using namespace std;

int minSkips(vector<int> &dist, int speed, int hoursBefore) {
    /* double类型精度偏差 */
    constexpr double EPS = 1e-8;
    int sum = 0;
    for (auto &x : dist) {
        sum += x;
    }
    //休息次数全部跳过，仍然不能按时到达
    /* 一定要转换为double类型 */
    if ((double) sum / speed > (double) hoursBefore) {
        return -1;
    }

    /* 动态规划 */
    /* dp数组dp[i][j] 代表在走过第i条道路时，跳过休息次数j次，所使用的时间 */
    vector<vector<double>> dp(dist.size(), vector<double>(dist.size(), INT_MAX));
    //走过第0条道路时，无需跳过休息，所用的时间为 (double) dist[0] / speed，记住类型转换
    dp[0][0] = (double) dist[0] / speed;
    for (int i = 1; i < dist.size(); ++i) {
        for (int j = 0; j <= i; ++j) {
            if (j == 0) {
                //j = 0 代表不跳过休息次数，则结果为走过上一条道路时不跳过休息次数的值上取整，加上这一次所使用的时间
                /*
                 * 由于double精度问题，ceil上取整可能不准确，所以要减去精度偏差再进行上取整
                 * 例如 9 在double下可能表示为 9.00000002，上取整则变为10，结果错误，故要减掉EPS
                 */
                dp[i][j] = ceil(dp[i - 1][j] - EPS) + (double) dist[i] / speed;
            } else if (j == i) {
                //j = i 代表跳过全部休息次数，则结果为走过上一条道路时跳过全部休息次数的值，加上这一次所使用的时间
                dp[i][j] = dp[i - 1][j - 1] + (double) dist[i] / speed;
            } else {
                //一般情况下，则判断是否跳过这一次的休息次数即可
                //如果这一次跳过，那么上一次不能跳过，反之，上一次必须跳过，取两者最小值，再加上这一次所使用的时间
                dp[i][j] = min(ceil(dp[i - 1][j] - EPS), dp[i - 1][j - 1]) + (double) dist[i] / speed;
            }
        }
    }
//    for (auto &v : dp) {
//        for (auto &x: v) {
//            cout << x << " ";
//        }
//        cout << endl;
//    }

    //在不超过规定时间时，返回最小的跳过的休息次数
    for (int i = 0; i < dist.size(); ++i) {
        if (dp[dist.size() - 1][i] <= (double) hoursBefore + EPS) {
            return i;
        }
    }

    return -1;
}

int main() {
    vector<int> dist = {1, 1, 1, 1, 1};
    int speed = 10000000;
    int hoursBefore = 1;
    cout << minSkips(dist, speed, hoursBefore) << endl;
}